package ceil03;

/**
 * 如果数组中存在元素，返回最大索引
 * 如果数组中不存在元素，返回upper
 * 在数学中，可以对浮点数做一个ceil的运算
 * ceil(5.0)=5   ceil(5.5)=6
 */
public class BinarySearch {
    // >target,返回最小值索引
    // ==target ，返回最大索引
    public static <E extends Comparable<E>> int ceil(E[] data, E target) {
        int u = upper(data, target);
        if (u - 1 > 0 && data[u - 1].compareTo(target) == 0) return u - 1;
        return u;
    }

    /**
     * 查找大于target的最小值的索引，搜索范围arr[l,r] r=arr.length
     * if（arr[mid]>target）r=mid;
     * if(arr[mid]<=target)l=mid+1;
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        int l = 0, r = data.length;
        //arr[l,r]中寻找解，不是一个合法的索引，但是是这个问题定义下的合法解答，这个问题中一定有问题的解答（即使没有解，也会返回data.length）
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) > 0) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 1, 3, 3, 5, 5};
        for (int i = 0; i < 71; i++) System.out.print(BinarySearch.ceil(arr, i) + " ");
        System.out.println();
    }
}
